package leetcode;

import java.util.HashMap;
import java.util.List;
import java.util.Map;
import java.util.Stack;

/**
 * 21. 合并两个有序链表
 * 将两个升序链表合并为一个新的 升序 链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。
 * 示例：
 * 输入：1->2->4, 1->3->4
 * 输出：1->1->2->3->4->4
 */

public class problems_021 {

    public static void main(String[] arge){
//        ListNode node11 = new ListNode(1);
//        ListNode node12 = new ListNode(2);
//        ListNode node13 = new ListNode(4);
//        ListNode node21 = new ListNode(1);
//        ListNode node22 = new ListNode(3);
//        ListNode node23 = new ListNode(4);
//        node11.next = node12;
//        node12.next = node13;
//        node21.next = node22;
//        node22.next = node23;


        ListNode node11 = null;
        ListNode node21 = new ListNode(0);

        System.out.println(new Solution().mergeTwoLists(node11, node21));
    }
    static class ListNode {
        int val;
        ListNode next;
        ListNode() {}
        ListNode(int val) { this.val = val; }
        ListNode(int val, ListNode next) { this.val = val; this.next = next; }
    }
    static class Solution {
        public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
            ListNode root = null;
            ListNode index = null;
            while (null != l1 || null != l2){
                int val = 0;
                if(null == l2 || (null != l1 && l1.val < l2.val)){
                    // 使用l1
                    val = l1.val;
                    l1 = l1.next;
                }else {
                    // 使用l2
                    val = l2.val;
                    l2 = l2.next;
                }
                if(null == root){
                    root = new ListNode(val);
                    index = root;
                }else {
                    index.next = new ListNode(val);
                    index = index.next;
                }
            }
            return root;
        }
    }
}
